package middle;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
 *
 * @author yuxuan.hu
 * */
public class KthLargestElementInAnArray {

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        solution1.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4);

        Solution2 solution2 = new Solution2();
        solution2.findKthLargest(new int[]{2,4,6,0,9},2);
    }
    /**
     * 优先队列，即大顶堆
     *
     * */
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(nums.length, (o1, o2) -> o2 - o1);
            for (int num : nums) {
                priorityQueue.add(num);
            }
            for (int i = 0; i < k-1; i++) {
                priorityQueue.poll();
            }
            return priorityQueue.isEmpty() ? 0 : priorityQueue.peek();
        }
    }

    /**
     * 利用快排分区的思想
     * 为啥我写的快排方法 时间这么长？？ 20多ms
     * 后面让基准数是随机的，速度提到了8ms，但是仍然没有官方的1ms快
     * 又通过static修饰符，速度提到了3ms。但是官方没有修饰符仍然只需要1ms啊。因为啥呢
     * */
    static class Solution1 {
        Random random = new Random();
        public int findKthLargest(int[] nums, int k) {
            return nums[partition(nums, 0, nums.length-1, k)];
        }

        static int partition(int[] nums, int left, int right, int k){
            if(left >= right){
                return left;
            }
            int pivot = (left + right) / 2;
            // 为什么需要在这里进行一次交换？因为我们需要将基准数放到第一位或者最后一位，后面的程序才会正确。
            // 如果基准数在中间会出现什么情况呢？ 举个例子 0 2 4 6 5 9 假设基准数是4，那么先从后面找比4小的，找到的会是2，那么2跟4进行交换，岂不是更乱了
            swap(nums, left, pivot);
            pivot = left;
            // 感觉速度慢的问题出在这个while循环
            while (left < right) {
                while(left < right && nums[right] >= nums[pivot]) {right--;}
                while(left < right && nums[left] <= nums[pivot]) {left++;}
                swap(nums, left, right);
            }

            swap(nums, left, pivot);
            if(k > (nums.length - left)){
                return partition(nums, 0, left-1, k);
            }else if(k < (nums.length - left)){
                return partition(nums, left+1, nums.length-1, k);
            }
            return left;

        }

        private static void swap(int[] nums, int left, int right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }


    /**
     * 快排官方版本
     *
     * */
    static class Solution2 {
        Random random = new Random();

        public int findKthLargest(int[] nums, int k) {
            return quickSelect(nums, 0, nums.length - 1, nums.length - k);
        }

        public int quickSelect(int[] a, int l, int r, int index) {
            int q = randomPartition(a, l, r);
            if (q == index) {
                return a[q];
            } else {
                return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
            }
        }

        public int randomPartition(int[] a, int l, int r) {
            int i = random.nextInt(r - l + 1) + l;
            swap(a, i, r);
            return partition(a, l, r);
        }

        // 这部分还是挺难理解的。 跟我们的双while循环相比确实更加巧妙。
        public int partition(int[] a, int l, int r) {
            int x = a[r], i = l - 1;
            for (int j = l; j < r; ++j) {
                if (a[j] <= x) {
                    swap(a, ++i, j);
                }
            }
            swap(a, i + 1, r);
            return i + 1;
        }

        public void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}
